#include <stdio.h>
#include <conio.h>
#include <String.h>
#include <stdlib.h>
#define Stack_Size 50 //定义栈的最大值
#define True 1        //定义true判断
#define False 0       //定义false判断
typedef struct
{
    char elem[Stack_Size];
    int top;
} Stack; //创建栈，数组类型为字符数组

//（2）栈的初始化
int InitStack(Stack *s) //初始化栈方法
{
    // top为-1表示栈空
    s->top = -1;
    return 1;
}

int Empty(Stack *s) //判断栈是否为空
{
    return (s->top == -1) ? True : False; //空返回True(1)非空返回False(0)
}

int Push(Stack *s, char c) //创建进栈方法
{
    if (s->top == Stack_Size)
        return False; //判断是否栈满
    else
    {
        s->top++;            //栈顶指针加1
        s->elem[s->top] = c; //将c赋值给栈顶元素
        return True;
    }
}
int Pop(Stack *s, char *c) //创建出栈方法
{
    if (s->top == -1)
        return False; //判断是否栈空
    else
    {
        *c = s->elem[s->top]; //将栈顶元素赋值给c
        s->top--;             //栈顶指针减1
        return True;
    }
}

int Get(Stack *s, char *c) //获取栈顶数据
{
    if (s->top == -1)
        return False; //判断是否栈空
    else
    {
        *c = s->elem[s->top]; //将栈顶的数据赋值给参数
        return True;
    }
}
int Match(char a, char b) //括号匹配方法
{
    if (a == '(' && b == ')')
        return True;
    else if (a == '[' && b == ']')
        return True;
    else if (a == '{' && b == '}')
        return True;
    else
        return False;
}
void BracketMatch(char *c) //判断字符串是否括号都匹配
{
    Stack S;       //创建空栈
    InitStack(&S); //初始化栈
    int flag = 0;  //用于判断字符串是否有括号
    char ch;
    for (int i = 0; c[i] != '\0'; i++) //遍历字符数组
    {
        switch (c[i])
        {
        case '(':
        case '[':
        case '{':
            Push(&S, c[i]); //如果遇到左括号，则将其置入栈顶
            flag = 1;       //表示有括号
            break;
        case ')':
        case ']':
        case '}':
            if (Empty(&S)) //当遇到右括号时，判断栈里是否还有左括号，如果为空则右括号多余
            {
                printf("\n右括号多余！\n");
                return;
            }
            else
            {
                Get(&S, &ch);        //获取栈顶的数据
                if (Match(ch, c[i])) //将栈顶的左括号与右括号进行匹配
                    Pop(&S, &ch);    //如果匹配成功则将其出栈
                else
                {
                    printf("\n对应的左右括号不同类！\n"); //不匹配
                    return;
                }
            }
        default: //遇到括号以外的数据，跳过
            break;
        }
    }
    if (Empty(&S) && flag == 1) //判断遍历结束后栈是否为空且是否有出现过左括号
        printf("\n括号匹配！\n");
    else if (flag == 1) //出现过左括号，但栈不为空，说明左括号多余
        printf("\n左括号多余!\n");
    else //没有出现过左括号且没有出现过右括号
        printf("\n没有可以匹配的括号！\n");
}
int main()
{
    char c[Stack_Size]; //创建空的字符数组
    do
    {
        printf("\n请输入一串字符：");
        scanf("%s", &c);      //输入字符串
        BracketMatch(c);      //判断括号匹配
    } while (getch() != '#'); //循环执行输入判断。直到键盘读取到’#’退出循环，结束程序
    printf("程序结束...");
    system("PAUSE");
}
